#pragma once

#include "decision.h"
#include <vector>
#include <list>

namespace solver
{

	class literal_node
	{
	public:

		literal_node *parent;
		literal lit;
		std::list<literal_node *> children;
		int string_id;
		bool used;

		literal_node() :
			parent(nullptr), 
			string_id(-1),
			used(false)
		{
			lit.ref = -1;
			lit.val = 0;
		}

		literal_node( literal_node *_parent, literal _lit, int _string_id ) 
			: parent( _parent ),
			lit( _lit ),
			string_id( _string_id ),
			used(false)
		{
			;
		}

		~literal_node()
		{
			;
		}

		decision_string to_string()
		{
			decision_string ds;
			literal_node *p = this;
			while (p->parent != nullptr)
			{
				ds.add(p->lit);
				p = p->parent;
			}
			return ds;
		}
	};


	class decision_string_collection
	{
		int string_id;
		literal_node *root;

		bool find_strings(literal_node *n, decision_string& dstr, std::list<literal_node *>& found_strings)
		{
			bool result = false;

			for (auto child : n->children)
			{
				if (dstr.exists_exact(child->lit))
				{
					if (child->string_id) 
					{
						found_strings.push_back(child);
						result = true;
						find_strings(child, dstr, found_strings);
					}
					else 
					{
						bool temp;
						temp = find_strings(child, dstr, found_strings);
						if (temp) 
						{
							result = true;
						}
					}
				}
			}

			return result;
		}

		int add(literal_node *n, decision_string& ds, decision_node *dsn)
		{
			int result = 0;
			if (dsn == nullptr)
			{
				string_id++;
				n->string_id = string_id;
				return string_id;
			}
			const literal& target = dsn->value;
			bool found = false;
			for (auto& child : n->children)
			{
				if (child->lit == target)
				{
					found = true;
					auto dsnn = ds.next(dsn);
					result = add(child, ds, dsnn);
					break;
				}
			}
			if (!found)
			{
				literal_node *new_node = new literal_node(n, target, false);
				n->children.push_back(new_node);
				auto dsnn = ds.next(dsn);
				result = add(new_node, ds, dsnn);
				count++;
			}

			return result;
		}

		void clear(literal_node *n)
		{
			for (auto& child : n->children)
			{
				clear(child);
			}
			n->children.clear();
			delete n;
		}

		int count;

	public:

		decision_string_collection() : count(0), string_id(0)
		{
			root = new literal_node();
		}

		virtual ~decision_string_collection()
		{
			if (root != nullptr)
			{
				clear(root);
				root = nullptr;
			}
			count = 0;
		}

		void clear()
		{
			string_id = 0;
			clear(root);
			root = new literal_node();
		}

		bool find_strings(decision_string& ds, std::list<literal_node *>& found_strings)
		{
			bool result;
			result = find_strings(root, ds, found_strings);
			return result;
		}

		int add(decision_string& ds)
		{
			int sid = 0;
			sid = add(root, ds, ds.first());
			return sid;
		}
		
		int get_count()
		{
			return count;
		}

		void self_test(std::list<std::string>& results)
		{

			decision_string rule1("ABC");
			decision_string rule2("A!BF");
			decision_string rule3("CD");
			decision_string rule4("!ABD");
			decision_string rule5("!B!E");

			add(rule1);
			add(rule2);
			add(rule3);
			add(rule4);
			add(rule5);

			decision_string test1("AB!CD");
			decision_string test2("AB*CD");
			decision_string test3("AB*CE*");

			std::list<literal_node *> fn1, fn2, fn3, fn4, fn5, fn6, fn7, fn8, fn9;

			if (!find_strings(rule1, fn1)) 
				results.push_back("rule1 invalid");

			if (!find_strings(rule2, fn2))
				results.push_back("rule2 invalid");

			if (!find_strings(rule3, fn3))
				results.push_back("rule2 invalid");

			if (!find_strings(rule3, fn3))
				results.push_back("rule2 invalid");

			if (!find_strings(rule4, fn4))
				results.push_back("rule4 invalid");

			if (!find_strings(rule5, fn5))
				results.push_back("rule5 invalid");

			// now, should be able to find 2 & 3 but not find 1
			if (find_strings(test1, fn6))
				results.push_back("test1 invalid");

			if (!find_strings(test2, fn7))
				results.push_back("test2 invalid");

			if (!find_strings(test3, fn8))
				results.push_back("test3 invalid");

		}
	};

	class production
	{
	public:
		decision_string match;
		literal product;
		int stringid;
	};

	typedef production *pproduction;

	class decision_result
	{
	public:
		bool matched;
	};

	class add_value_result
	{
	public:
		bool success;
	};

	class conflict_mapping 
	{
	public:

		pproduction match_prod;
		decision_string match_mapping;
		int match_mask;
		int match_value;

		conflict_mapping() : match_prod(nullptr)
		{

		}
	};

	class variable_mapping
	{
	public:
		int ref;
		int value;
	};

	class multiconflict_iterator
	{
	private:
		std::list<conflict_mapping *> conflicts;
		decision_string variables;
		int max_value;
		int current_value;

		bool test_conflict(conflict_mapping *cm)
		{
			return ( current_value & cm->match_mask ) == cm->match_value;
		}

		void debug_variables()
		{
			auto fn = variables.first();
			while (fn != nullptr)
			{
				char buff[128];
				sprintf(buff, "%d", fn->value.val);
				fn = variables.next(fn);
				::OutputDebugString(buff);
			}
			::OutputDebugString("\n");
		}

		bool increment(decision_node *fn = nullptr)
		{
			current_value++;
			if (current_value < 0)
				return false;

			return true;
		}

	public:

		std::function<void(const char *message)> progress_func;
		decision_string last_result;

		multiconflict_iterator(int _max_value = 1) :max_value(_max_value)
		{
		}

		virtual ~multiconflict_iterator()
		{
			for (auto cmi = conflicts.begin(); cmi != conflicts.end(); cmi++)
			{
				auto c = *cmi;
				if (c != nullptr)
					delete c;
			}

			conflicts.clear();
			variables.clear();
		}

		int size()
		{
			return variables.size();
		}

		bool add(pproduction prod)
		{
			for (auto cmi : conflicts) 
			{
				if (cmi->match_prod == prod) 
				{
					return false;
				}
			}

			conflict_mapping *cm = new conflict_mapping();
			cm->match_prod = prod;
			cm->match_value = 0;
			int bitidx = 0;
			for (auto mpv = prod->match.first(); mpv != nullptr; mpv = prod->match.next(mpv))
			{
				if (!variables.exists(mpv->key)) 
				{
					literal ly;
					ly.ref = mpv->key;
					ly.val = mpv->value.val;
					variables.add(ly);
				}
				literal lx;
				lx.ref = mpv->key;
				lx.val = bitidx;
				cm->match_mapping.add(lx);
				if (cm->increment_ref == -1 || cm->increment_ref > lx.ref) 
				{
					cm->increment_ref = lx.ref;
				}
				cm->match_value |= (mpv->value.val << bitidx);
				bitidx++;
			}

			conflicts.push_back(cm);

			auto n = variables.find_node(cm->increment_ref);
			increment(n);

			return true;
		}

		bool get_first(decision_string& solution)
		{
			for (auto fn = variables.first(); fn != nullptr; fn = variables.next(fn))
			{
				fn->value.val = 0;
			}
		retry1:
			debug_variables();
			for (auto cm : conflicts)
			{
				if (test_conflict(cm))
				{
					bool incremented = increment(nullptr);
					if (incremented)
						goto retry1;
					else
						return false;
				}
			}

			last_result.clear();

			for (auto v = variables.first(); v != nullptr; v = variables.next(v))
			{
				last_result.add(v->value);
			}

			solution.fold(last_result);

			return true;

		}

		bool get_next(decision_string& solution)
		{
			bool incremented;

			retry1:
			incremented = increment(nullptr);
			if (!incremented)
				return false;
			debug_variables();

			for (auto cm : conflicts)
			{
				if (test_conflict(cm))
				{
					goto retry1;
				}
			}

			last_result.clear();

			for (auto v = variables.first(); v != nullptr; v = variables.next(v))
			{
				last_result.add(v->value);
			}

			solution.fold(last_result);

			return true;
		}

	
		bool try_next(decision_string& solution)
		{

			bool incremented;
			
		retry1:

			for (auto cm : conflicts)
			{
				if (test_conflict(cm)) 
				{
					auto n = variables.find_node(cm->increment_ref);
					incremented = increment(n);
					if (!incremented)
						return false;
					goto retry1;
				}
			}

			last_result.clear();

			for (auto v = variables.first(); v != nullptr; v = variables.next(v))
			{
				last_result.add(v->value);
			}

			solution.fold(last_result);

			return true;
		}
	};

}
